1. Field of the Invention
The present invention relates to a fast Fourier transform circuit and a fast Fourier transform method, and particularly relates to a fast Fourier transform circuit and fast Fourier transform method for applying a discrete-time Fourier transform computation to 2n points of input data, each of a predetermined number of bits (n being a natural number greater than 0), by dividing into a plurality of stages and performing butterfly computations.
2. Description of the Related Art
With the advance of digital technology in recent years, broadcasts such as terrestrial television broadcasts and the like are shifting from analog broadcasting to digital broadcasting. For such digital broadcasts, an orthogonal frequency division multiplexing system below referred to as OFDM) is employed as a modulation system. For demodulation of a carrier wave in OFDM, fast Fourier transforms (below referred to as FFT) are utilized.
These fast Fourier transforms are a technology for reducing the computation volume of a discrete-time Fourier transform below referred to as a DFT). A great many computation technologies have been proposed for these fast Fourier transforms. One generally well-known computation technology is a Cooley-Tukey-based computation technology which performs a discrete-time Fourier transform by performing butterfly computations on input data, divided into a plurality of stages (steps). As a related technology, Japanese patent Application Laid-Open (JP-A) No. 5-266059 has disclosed a technique which improves a processing efficiency of these butterfly computations.
Herebelow, a frequency-thirning Cooley-Tukey-type fast Fourier transform with a radix of 2 will be described. Below, a number of data points N of a discrete-time Fourier transform (a number of data samples) is 4.
A definition equation of a discrete-time Fourier transform is shown by the following equation (1). WN in equation (1) is a twiddle factor.
                              X          ⁡                      (            k            )                          =                              ∑                          n              =              0                                      N              -              1                                ⁢                                          ⁢                                    x              ⁡                              (                n                )                                      ·                          W              N              nk                                                          (        1        )            
Here, WN=e−j2π/N 
Hence, a discrete-time Fourier transform with the number of data points being 4 is expressed by the following parallel matrix equation of equation (2).
                              [                                                                      X                  ⁡                                      (                    0                    )                                                                                                                        X                  ⁡                                      (                    1                    )                                                                                                                        X                  ⁡                                      (                    2                    )                                                                                                                        X                  ⁡                                      (                    3                    )                                                                                ]                =                              [                                                                                                      W                      4                      0                                        ⁢                                          W                      4                      0                                        ⁢                                          W                      4                      0                                        ⁢                                          W                      4                      0                                                                                                                                                              W                      4                      0                                        ⁢                                          W                      4                      1                                        ⁢                                          W                      4                      2                                        ⁢                                          W                      4                      3                                                                                                                                                              W                      4                      0                                        ⁢                                          W                      4                      2                                        ⁢                                          W                      4                      4                                        ⁢                                          W                      4                      6                                                                                                                                                              W                      4                      0                                        ⁢                                          W                      4                      3                                        ⁢                                          W                      4                      6                                        ⁢                                          W                      4                      9                                                                                            ]                    ·                      [                                                                                x                    ⁡                                          (                      0                      )                                                                                                                                        x                    ⁡                                          (                      1                      )                                                                                                                                        x                    ⁡                                          (                      2                      )                                                                                                                                        x                    ⁡                                          (                      3                      )                                                                                            ]                                              (        2        )            
In a Cooley-Tukey-type computation technique, each X(k) (k=1, 2, 3, 4) in the above equation (2) is substituted as in the following equation (3).
                              [                                                                      X                  ⁡                                      (                    0                    )                                                                                                                        X                  ⁡                                      (                    2                    )                                                                                                                        X                  ⁡                                      (                    1                    )                                                                                                                        X                  ⁡                                      (                    3                    )                                                                                ]                =                              [                                                                                                      W                      4                      0                                        ⁢                                          W                      4                      0                                        ⁢                                          W                      4                      0                                        ⁢                                          W                      4                      0                                                                                                                                                              W                      4                      0                                        ⁢                                          W                      4                      2                                        ⁢                                          W                      4                      4                                        ⁢                                          W                      4                      6                                                                                                                                                              W                      4                      0                                        ⁢                                          W                      4                      1                                        ⁢                                          W                      4                      2                                        ⁢                                          W                      4                      3                                                                                                                                                              W                      4                      0                                        ⁢                                          W                      4                      3                                        ⁢                                          W                      4                      6                                        ⁢                                          W                      4                      9                                                                                            ]                    ·                      [                                                                                x                    ⁡                                          (                      0                      )                                                                                                                                        x                    ⁡                                          (                      1                      )                                                                                                                                        x                    ⁡                                          (                      2                      )                                                                                                                                        x                    ⁡                                          (                      3                      )                                                                                            ]                                              (        3        )            
The 4×4 matrix in equation (3) can be expressed as shown in the following equation (4).
                                          W            ^                    4                =                  [                                                                                          W                    4                    0                                    ⁢                                      W                    4                    0                                    ⁢                                      W                    4                    0                                    ⁢                                      W                    4                    0                                                                                                                                            W                    4                    0                                    ⁢                                      W                    4                    2                                    ⁢                                      W                    4                    4                                    ⁢                                      W                    4                    6                                                                                                                                            W                    4                    0                                    ⁢                                      W                    4                    1                                    ⁢                                      W                    4                    2                                    ⁢                                      W                    4                    3                                                                                                                                            W                    4                    0                                    ⁢                                      W                    4                    3                                    ⁢                                      W                    4                    6                                    ⁢                                      W                    4                    9                                                                                ]                                    (        4        )            
Now, as is shown in FIG. 9, the twiddle factor WN can be expressed as points on a unit circle in a complex plane. Therefore, the relationships shown in the following equations (5) and (6) apply to the twiddle factor.WN2k=WN/2k  (5)WNnk=WN((nk))N  (6)
Therefore, equation (3) can be rewritten as equation (7).
                                                                                          [                                                                                                              X                          ⁡                                                      (                            0                            )                                                                                                                                                                                        X                          ⁡                                                      (                            2                            )                                                                                                                                                                                        X                          ⁡                                                      (                            1                            )                                                                                                                                                                                        X                          ⁡                                                      (                            3                            )                                                                                                                                ]                                =                                ⁢                                                      [                                                                                                                                                      W                              4                              0                                                        ⁢                                                          W                              4                              0                                                        ⁢                                                          W                              4                              0                                                        ⁢                                                          W                              4                              0                                                                                                                                                                                                                                      W                              4                              0                                                        ⁢                                                          W                              4                              2                                                        ⁢                                                          W                              4                              0                                                        ⁢                                                          W                              4                              2                                                                                                                                                                                                                                      W                              4                              0                                                        ⁢                                                          W                              4                              1                                                        ⁢                                                          W                              4                              2                                                        ⁢                                                          W                              4                              3                                                                                                                                                                                                                                      W                              4                              0                                                        ⁢                                                          W                              4                              3                                                        ⁢                                                          W                              4                              2                                                        ⁢                                                          W                              4                              1                                                                                                                                            ]                                    ·                                      [                                                                                                                        x                            ⁡                                                          (                              0                              )                                                                                                                                                                                                        x                            ⁡                                                          (                              1                              )                                                                                                                                                                                                        x                            ⁡                                                          (                              2                              )                                                                                                                                                                                                        x                            ⁡                                                          (                              3                              )                                                                                                                                            ]                                                                                                                          =                                ⁢                                                      [                                                                                                                                                      W                              ^                                                        2                                                                                                                                                              W                              ^                                                        2                                                                                                                                                                                                                                          W                                ^                                                            2                                                        ⁢                                                          Λ                              2                                                                                                                                                                                          -                                                                                                W                                  ^                                                                2                                                                                      ⁢                                                          Λ                              2                                                                                                                                            ]                                    ·                                      [                                                                                                                        x                            ⁡                                                          (                              0                              )                                                                                                                                                                                                        x                            ⁡                                                          (                              1                              )                                                                                                                                                                                                        x                            ⁡                                                          (                              2                              )                                                                                                                                                                                                        x                            ⁡                                                          (                              3                              )                                                                                                                                            ]                                                                                      ⁢                                  ⁢                                            W              ^                        2                    =                      [                                                                                                      W                      2                      0                                        ⁢                                          W                      2                      0                                                                                                                                                              W                      2                      0                                        ⁢                                          W                      2                      1                                                                                            ]                          ⁢                                  ⁢                              Λ            2                    =                      [                                                                                W                    4                    0                                                                    0                                                                              0                                                                      W                    4                    1                                                                        ]                                              (        7        )            
Hence, if equation (3) is expressed using a 2×2 zero matrix O2 and a 2×2 unit matrix I2, the following equation (8) is produced.
                                                                                             [                                                                                                              X                          ⁡                                                      (                            0                            )                                                                                                                                                                                        X                          ⁡                                                      (                            2                            )                                                                                                                                                                                        X                          ⁡                                                      (                            1                            )                                                                                                                                                                                        X                          ⁡                                                      (                            3                            )                                                                                                                                ]                                =                                ⁢                                                      [                                                                                                                                                      W                              ^                                                        2                                                                                                                                o                            2                                                                                                                                                                            o                            2                                                                                                                                                              W                              ^                                                        2                                                                                                                ]                                    ·                                      [                                                                                                                        I                            2                                                                                                                                o                            2                                                                                                                                                                            o                            2                                                                                                                                I                            2                                                                                                                ]                                    ·                                      [                                                                                                                        I                            2                                                                                                                                I                            2                                                                                                                                                                            I                            2                                                                                                                                -                                                          I                              2                                                                                                                                            ]                                    ·                                      [                                                                                                                        x                            ⁡                                                          (                              0                              )                                                                                                                                                                                                        x                            ⁡                                                          (                              1                              )                                                                                                                                                                                                        x                            ⁡                                                          (                              2                              )                                                                                                                                                                                                        x                            ⁡                                                          (                              3                              )                                                                                                                                            ]                                                                                                                          =                                ⁢                                                      [                                                                                            1                                                                          1                                                                          0                                                                          0                                                                                                                      1                                                                                                      -                            1                                                                                                    0                                                                          0                                                                                                                      0                                                                          0                                                                          1                                                                          1                                                                                                                      0                                                                          0                                                                          1                                                                                                      -                            1                                                                                                                ]                                    ·                                      [                                                                                            1                                                                          0                                                                          0                                                                          0                                                                                                                      0                                                                          1                                                                          0                                                                          0                                                                                                                      0                                                                          0                                                                                                      W                            4                            0                                                                                                    0                                                                                                                      0                                                                          0                                                                          0                                                                                                      W                            4                            0                                                                                                                ]                                    ·                                                                                                                        ⁢                                                      [                                                                                            1                                                                          0                                                                          1                                                                          0                                                                                                                      0                                                                          1                                                                          0                                                                          1                                                                                                                      1                                                                          0                                                                          1                                                                          0                                                                                                                      0                                                                          1                                                                          0                                                                                                      -                            1                                                                                                                ]                                    ·                                      [                                                                                                                        x                            ⁡                                                          (                              0                              )                                                                                                                                                                                                        x                            ⁡                                                          (                              1                              )                                                                                                                                                                                                        x                            ⁡                                                          (                              2                              )                                                                                                                                                                                                        x                            ⁡                                                          (                              3                              )                                                                                                                                            ]                                                                                                            (          8          )                    
That is, a discrete-time Fourier transform with the number of data points N being 4 can be decomposed to be a product or matrices constituted of discrete-time Fourier transforms with numbers of data points N being 2. Such decomposition is not limited to cases in which the number of data points N is 4 but generally applies to cases in which the number of data points N is 2n (where n is a natural number greater than 0).
The decomposition shown in the above equation (8) can be represented as shown in FIG. 10, being represented by a combination of the butterfly computation shown in FIG. 11.
Similarly, taking a discrete-time Fourier transform with the number of data points N being 8 as an example, the discrete-time Fourier transform with the number of data points N of 8 can be decomposed into discrete-time Fourier transforms with numbers of data points N of 4 by sorting the X(k), and the discrete-time Fourier transforms with numbers of data points N of 4 can be further decomposed into discrete-time Fourier transforms with numbers of data points N of 2. This decomposition can be represented as in FIG. 12.
As shown in FIG. 10 (a data point count N=4 fast Fourier transform) and FIG. 12 (a data point count N=8 fast Fourier transform), a fast Fourier transform can be implemented by a combination of butterfly computations, and a number of stages of these butterfly computations can be expressed as log2 N. For example, in the case of a data point count N=8 fast Fourier transform, the number of stages is log2 8=3.
FIG. 13 shows an example of a fixed-point fast Fourier transform circuit 10′ which implements a Cooley-Tukey-type fast Fourier transform.
Operations of this fast Fourier transform circuit 10′, with the radix being 2, will be briefly described for a case of performing a fast Fourier transform with the number of data points N being 8.
(1) Input data to be inputted to the fast Fourier transform circuit 10′ is memorized at an FFT input data storage RAM 12′. A stage control circuit 14′ outputs a stage signal (a signal indicating which stage is in operation) and controls operations of a selector 16′ and an FFT computation section 22′. Initially, the stage control circuit 14′ outputs a stage signal indicating a first stage.
(2) When the stage signal outputted by the stage control circuit 14′ indicates the first stage, data from the FFT input data storage RAM 12′ is selected by the selector 16′, and the data from the FFT input data storage RAM 12′ is inputted to the FFT computation section 22′.
(3) The FFT computation section 22′ reads respective twiddle factors corresponding to the stage indicated by the stage signal from a twiddle factor table 18′, which is memorized at a twiddle factor memorization section 20′, and performs butterfly computations on the data that have been inputted using the respective twiddle factors that have been read.
(4) Results of the butterfly computations are memorized in an FFT computation result storage RAM 28′. When the butterfly computation results have all been memorized to the FFT computation result storage RAM 28′, the stage control circuit 14′ outputs a stage signal indicating the next stage.
(5) When the stage signal outputted by the stage control circuit 14′ indicates the second or a subsequent stage, data from the FFT computation result storage RAM 28′ is selected by the selector 16′, and the data from the FFT computation result storage RAM 28′ is inputted to the FFT computation section 22′.
(6) Thereafter, the operations of (3) to (5) above are repeated, for a number of stages corresponding to the data point count N.
(7) After the butterfly computations for the number of stages have been completed (i.e., if the data point count N is 8, after three stages have been completed), the data that has been memorized to the FFT computation result storage RAM 28′ serves as output data of the fast Fourier transform.
Now, in a case in which the above-described Cooley-Tukey-type fast Fourier transform computation is practically implemented in hardware, data of unlimited bit widths cannot be held in the FFT input data storage RAM 12′, the FFT computation result storage RAM 28′, the FFT computation section 22′ and the like (FIG. 13). Therefore, a bit width limitation is inherent in the circuit.
For example, bit widths for one data point in the FFT input data storage RAM 12′ and the FFT computation result storage RAM 28′ may be limited to 16 bits, and a bit width of each twiddle factor WNi may be 10 bits. In such a case, as shown in FIG. 14, one cycle of addition of 16 bits and one multiplication of an addition result with the twiddle factor are performed. Therefore, data widths of output data points which are outputted as results of the butterfly computations by the FFT computation section 22′ are up to 27 bits.
However, the bit width of the FFT computation result storage RAM 28′ is limited to 16 bits. Therefore, in this conventional fast Fourier transform circuit 10′, as shown in FIG. 15, it is necessary to provide a bit extraction section 24′, to extract 16 bits of data from the 27 bits with the bit extraction section 24′, and store the 16 bits of data in the FFT computation result storage RAM 28′.
At this bit extraction section 24′, which 16 bits of data to extract from the 27 bits is specified beforehand. For example, extraction may always be fixedly applied, to always extract the most significant 16 bits of data of a 27-bit signal, or the like.
However, if the range of data to be extracted by the bit extraction section 24′ is fixed thus, the data extraction range may not be an appropriate range, depending on characteristics of input data that are inputted to the fast Fourier transform circuit 10′ (the size of an amplitude value, whether randomness is high or low, whether the data is an impulse with a localized peak, and so forth). Hence, if the data extraction range is not a suitable range, overflows/underflows, errors and the like may occur during computation of a fast Fourier transform, and a final computation error of the fast Fourier transform may be large, which is a problem.